package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
 **/
public class No063 {
    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了40.53%的用户
     * 内存消耗：41.4 MB, 在所有 Java 提交中击败了5.31%的用户
     */
    public int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];
        int preMin = prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.max(dp[i - 1], prices[i] - preMin);
            preMin = Math.min(prices[i], preMin);
        }

        return dp[prices.length - 1];
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.4 MB, 在所有 Java 提交中击败了5.31%的用户
     */
    public int maxProfit2(int[] prices) {
        int maxProfit = 0;
        int preMin = Integer.MAX_VALUE;

        for (int price : prices) {
            preMin = Math.min(price, preMin);
            maxProfit = Math.max(maxProfit, price - preMin);
        }

        return maxProfit;
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.5 MB, 在所有 Java 提交中击败了5.31%的用户
     */
    public int maxProfit3(int[] prices) {
        if (prices.length < 2) return 0;
        int maxProfit = 0;
        int preMin = prices[0];

        for (int price : prices) {
            if (price > preMin) maxProfit = Math.max(maxProfit, (price - preMin));
            else if (price < preMin) preMin = price;
        }

        return maxProfit;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了98.84%的用户
     * 内存消耗：41.3 MB, 在所有 Java 提交中击败了5.31%的用户
     */
    public int maxProfit4(int[] prices) {
        if (prices.length < 2) return 0;
        int maxProfit = 0;
        int preMin = prices[0];

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] <= preMin) preMin = prices[i];
            else maxProfit = Math.max(maxProfit, prices[i] - preMin);
        }

        return maxProfit;
    }
}
